/*
 * @lc app=leetcode.cn id=5 lang=cpp
 * @lcpr version=30204
 *
 * [5] 最长回文子串
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    // 暴力求解 遇到很长的字符串就会超出内存限制
    // bool IsPalindrome(string s, int left, int right) 判断是否是回文字符串
    // {
    //     while (left < right && s[left] == s[right])
    //     {
    //         left++;
    //         right--;
    //     }
    //     if (left < right)
    //         return false;
    //     else
    //         return true;
    // }
    // string longestPalindrome(string s)
    // {
    //     int n = s.size();
    //     int maxlength = 0;

    //     string res;
    //     for (int i = 0; i < n; ++i)
    //     {
    //         for (int j = i+1; j < n; ++j)  （0，1）（0，2）...（1，2）（1，3）...这样子一个一个匹配
    //         {
    //             if (IsPalindrome(s, i, j))
    //             {
    //                 string tmp = s.substr(i, j - i + 1);     是回文字符串就与记录的最长回文字符串相比较，更新最长的
    //                 if (res.size() < tmp.size())
    //                 {
    //                     res = tmp;
    //                 }
    //             }
    //         }
    //     }
    //     return res;
    // }

    string longestPalindrome(string s)
    {
        // 动态规划
        int n = s.size();
        if (n < 2)
        {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++)
        {
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++)    // 长度从2开始
        {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) //左边界从0下标开始
            {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n)
                {
                    break;
                }

                if (s[i] != s[j])       // 在两个边界之间的字符串如果是回文就需要前后相同，不相同就说明不是
                {
                    dp[i][j] = false;
                }
                else
                {
                    if (j - i < 3)      // 字串长度为2，然后又前后相等，说明为回文
                    {
                        dp[i][j] = true;
                    }
                    else
                    {
                        dp[i][j] = dp[i + 1][j - 1];    // 长度很长的时候，前后两字符相同，那回文就取决于中间的字符串
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen)
                {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};
// @lc code=end

/*
// @lcpr case=start
// "babad"\n
// @lcpr case=end

// @lcpr case=start
// "cbbd"\n
// @lcpr case=end

 */
